#include <iostream>
#include <vector>
#include <algorithm>

//1  2  3  4    
//5  6  7  8
//4  4  6  7
//9  1  3  5

//1  5  4  9    
//2  6  4  1
//3  7  6  3
//4  8  7  5

//9  4  5  1    
//1  4  6  2
//3  6  7  3
//5  7  8  4

void Change(std::vector<std::vector<int>>& matrix)
{
	int m = matrix.size();
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < i; j++)
		{
			std::swap(matrix[i][j], matrix[j][i]);
		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m / 2; j++)
		{
			std::swap(matrix[i][j], matrix[i][m - j - 1]);
		}
	}
}

int main()
{
	std::vector<std::vector<int>> matrix = { {1, 2, 3, 4, 5}, {6, 7, 8 ,9, 10}, {11, 12, 13, 14, 15 }, { 16, 17, 18 ,19, 20 },{21, 22, 23, 24, 25 } };
	Change(matrix);
	for (int i = 0; i < matrix.size(); i++)
	{
		for (int j = 0; j < matrix[0].size(); j++)
		{
			std::cout << matrix[i][j] << " ";
		}
		std::cout << std::endl;
	}

	return 0;
}
class Solution
{
	int ret = -1000;
public:
	int maxPathSum(TreeNode* root)
	{
		dfs(root);
		return ret;
	}
	int dfs(TreeNode* root)
	{
		if (root == nullptr) return 0;
		int left = max(0, dfs(root->left));
		int right = max(0, dfs(root->right));
		ret = max(ret, root->val + left + right);
		return root->val + max(left, right);
	}
};
class Solution
{
	stack<TreeNode*> st1;
	stack<TreeNode*> st2;
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
	{
		GetPath(root, p, st1);
		GetPath(root, q, st2);

		int s1 = st1.size(), s2 = st2.size();
		int dif = abs(s1 - s2);
		while (dif--)
		{
			if (s1 > s2) st1.pop();
			else st2.pop();
		}
		while (st1.top() != st2.top())
		{
			st1.pop();
			st2.pop();
		}
		return st1.top();
	}
	bool GetPath(TreeNode* root, TreeNode* t, stack<TreeNode*>& st)
	{
		if (root == nullptr) return false;
		st.push(root);
		if (root == t) return true;
		bool left = GetPath(root->left, t, st);
		if (left == true) return true;
		bool right = GetPath(root->right, t, st);
		if (right == true) return true;
		st.pop();
		return false;
	}
};

